home *** CD-ROM | disk | FTP | other *** search
/ Deutsche Edition 1 / Deutsche Edition 1.iso / amok / amok_lha / amok24.lha / Updates / Trees.mod < prev    next >
Text File  |  1993-08-15  |  4KB  |  184 lines
  1. (**********************************************************************
  2.  
  3.     :Program.    Trees.mod
  4.     :Contents.   generic data type: binary trees
  5.     :Author.     Nicolas Benezan [bne]
  6.     :Address.    Postwiesenstr. 2, D7000 Stuttgart 60
  7.     :Phone.      711/333679
  8.     :Copyright.  Public Domain
  9.     :Language.   Modula-2
  10.     :Translator. M2Amiga A+L V3.2d
  11.     :Imports.    TaskMemory [bne]
  12.     :History.    V1.0 [bne] 25.Jun.1989
  13.     :Update.     [bne] 15.Jul.1989 cosmetics, inline dokumentation
  14.     :History.    V1.1 [bne] 13.Aug.1989 (bugs fixed, + InsertMode)
  15.  
  16. **********************************************************************)
  17.  
  18. IMPLEMENTATION MODULE Trees;
  19.  
  20. FROM Exec       IMPORT CopyMem;
  21. FROM SYSTEM     IMPORT ADDRESS, ADR, BYTE;
  22. FROM TaskMemory IMPORT Allocate, Deallocate;
  23.  
  24. CONST
  25.   NodeSize=SIZE(TreeNode);
  26.  
  27. TYPE
  28.   Tree=POINTER TO Root;
  29.   Root=RECORD
  30.     rootNode: TreeNodePtr;
  31.     numNodes: LONGINT;
  32.     cmp: CompareProc;
  33.     dupKeys: BOOLEAN;
  34.   END;
  35.  
  36. PROCEDURE InitTree(VAR T: Tree;
  37.                        AllowDupKeys: BOOLEAN;
  38.                        Cmp: CompareProc): BOOLEAN;
  39.   BEGIN
  40.     TreesAllocProc(T, SIZE(Root));
  41.     IF T#NIL THEN
  42.       WITH T^ DO
  43.         rootNode:=NIL;
  44.         numNodes:=0;
  45.         cmp:=Cmp;
  46.         dupKeys:=AllowDupKeys;
  47.       END;
  48.       RETURN TRUE;
  49.     END;
  50.     RETURN FALSE;
  51.   END InitTree;
  52.  
  53. PROCEDURE DiscardTree(VAR T: Tree);
  54.   VAR
  55.     Next:TreeNodePtr;
  56.  
  57.   PROCEDURE Delete(Node: TreeNodePtr);
  58.     BEGIN
  59.       WHILE Node#NIL DO
  60.         Delete(Node^.l);
  61.         Next:=Node^.r;
  62.         TreesDeallocProc(Node);
  63.         Node:=Next;
  64.       END;
  65.     END Delete;
  66.  
  67.   BEGIN
  68.     Delete(T^.rootNode);
  69.     TreesDeallocProc(T);
  70.   END DiscardTree;
  71.  
  72. PROCEDURE Add(T: Tree;
  73.               Node: ADDRESS): BOOLEAN;
  74.   VAR
  75.     NodePtr, Parent: TreeNodePtr;
  76.     Diff: INTEGER;
  77.   BEGIN
  78.     NodePtr:=Node;
  79.     WITH NodePtr^ DO
  80.       l:=NIL;
  81.       r:=NIL;
  82.     END;
  83.     WITH T^ DO
  84.       INC(numNodes);
  85.       Parent:=rootNode;
  86.       IF Parent=NIL THEN
  87.         rootNode:=NodePtr;
  88.         RETURN TRUE
  89.       END;
  90.       LOOP
  91.         Diff:=cmp(LONGINT(NodePtr)+NodeSize, LONGINT(Parent)+NodeSize);
  92.         IF Diff<0 THEN
  93.           IF Parent^.l=NIL THEN
  94.             Parent^.l:=NodePtr;
  95.             RETURN TRUE;
  96.           ELSE
  97.             Parent:=Parent^.l;
  98.           END;
  99.         ELSIF dupKeys OR (Diff#0) THEN
  100.           IF Parent^.r=NIL THEN
  101.             Parent^.r:=NodePtr;
  102.             RETURN TRUE;
  103.           ELSE
  104.             Parent:=Parent^.r;
  105.           END;
  106.         ELSE
  107.           RETURN FALSE;
  108.         END; (* IF *)
  109.       END; (* LOOP *)
  110.     END; (* WITH *)
  111.   END Add;
  112.  
  113. PROCEDURE Put(T: Tree;
  114.               Data: ARRAY OF BYTE): ADDRESS;
  115.   VAR
  116.     Node: TreeNodePtr;
  117.     DataSize: CARDINAL;
  118.   BEGIN
  119.     DataSize:=HIGH(Data)+1;
  120.     TreesAllocProc(Node, NodeSize+DataSize);
  121.     IF Node#NIL THEN
  122.       CopyMem(ADR(Data), LONGINT(Node)+NodeSize, DataSize);
  123.       IF Add(T, Node) THEN
  124.         RETURN LONGINT(Node)+NodeSize
  125.       ELSE
  126.         TreesDeallocProc(Node);
  127.       END;
  128.     END;
  129.     RETURN NIL;
  130.   END Put;
  131.  
  132. PROCEDURE Get(T: Tree;
  133.               Data: ADDRESS): ADDRESS;
  134.   VAR
  135.     Node: TreeNodePtr;
  136.     Diff: INTEGER;
  137.   BEGIN
  138.     WITH T^ DO
  139.       Node:=rootNode;
  140.       WHILE Node#NIL DO
  141.         Diff:=cmp(Data, LONGINT(Node)+NodeSize);
  142.         IF Diff<0 THEN
  143.           Node:=Node^.l;
  144.         ELSIF Diff=0 THEN
  145.           INC(Node, NodeSize);
  146.           RETURN Node;
  147.         ELSE
  148.           Node:=Node^.r;
  149.         END;
  150.       END;
  151.       RETURN NIL;
  152.     END;
  153.   END Get;
  154.  
  155. PROCEDURE Do(T: Tree;
  156.              Action: TreeProc;
  157.              Ref: ADDRESS);
  158.  
  159.   PROCEDURE Visit(Node: TreeNodePtr);
  160.     BEGIN
  161.       WHILE Node#NIL DO
  162.         WITH Node^ DO
  163.           Visit(l);
  164.           Action(LONGINT(Node)+NodeSize, Ref);
  165.           Node:=r;
  166.         END;
  167.       END;
  168.     END Visit;
  169.  
  170.   BEGIN
  171.     Visit(T^.rootNode);
  172.   END Do;
  173.  
  174. PROCEDURE NodesInTree(T: Tree): LONGINT;
  175.   BEGIN
  176.     RETURN T^.numNodes
  177.   END NodesInTree;
  178.  
  179. BEGIN
  180.   TreesAllocProc:=Allocate;
  181.   TreesDeallocProc:=Deallocate;
  182. END Trees.
  183.  
  184.